package tree.递归;

import po.TreeNode;

import java.text.Collator;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 有序数组转换为二叉搜索树108.java
 * @Description  https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 *
 * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树
 *
 * @createTime 2021年03月30日 12:56:00
 */
public class 有序数组转换为二叉搜索树108 {

    int[] nums;

    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return buildTree(0, nums.length - 1);
    }

    private TreeNode buildTree(int start, int end) {
        if (start > end) {
            return null;
        }
        //计算中间节点的索引，也就是根节点
        int mid = start+(end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildTree(start, mid - 1);
        root.right = buildTree(mid + 1, end);
        return root;
    }

    public static void main(String[] args) {
        List<String> list=new ArrayList<>();
        list.add("3测试简称");
        list.add("简称排序1测试");
        list.add("a别名");
        list.add("简称2排序");
        Comparator<Object> compare = Collator.getInstance(java.util.Locale.CHINA);
        list.sort(compare);
        System.out.println(list);
    }
}
